#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***************************************************************
 *函数名称：  help
 *函数功能：对链表操作的菜单
 *返回值类型：void
 ****************************************************************/
void help(void) {
    printf("****************************************************************\n");
    printf("*1 ：创建一个链表          2 ：销毁链表                         *\n");
    printf("*3 ：清空链表              4 ：链表判空                         *\n");
    printf("*5 ：链表长度              6 ：获取元素                         *\n");
    printf("*7 ：查找元素              8 ：获取前驱元素                     *\n");
    printf("*9 ：获取后继元素          10：插入元素                         *\n");
    printf("*11：删除元素              12：遍历线性表                       *\n");
    printf("*13：链表写文件            14：链表读文件                       *\n");
    printf("*15：链表反转              16：删除倒数第n个结点                *\n");
    printf("*17：链表排序              18：菜单      0 ：退出               *\n");
    printf("****************************************************************\n");
}

/***************************************************************
 *函数名称：  InitList
 *函数功能：线性表L不存在，构造一个空的线性表，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status InitList(LinkList &L) {

    if (L != NULL)
        return INFEASIBLE;
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        return ERROR;
    L->next = NULL;
    return OK;
}

/***************************************************************
 *函数名称：  inputLIst
 *函数功能：如果线性表不存在返回INFEASIBLE，否则创建一个线性表输入元素的值
 *返回值类型：status
 ****************************************************************/
status inputLIst(LinkList L) {
    if (L == NULL)
        return INFEASIBLE;
    int len, tem;
    printf("请输入线性表长度\n");
    scanf("%d", &len);
    LinkList p = L;
    for (int i = 0; i < len; i++) {
        p->next = (LinkList)malloc(sizeof(LNode));
        p = p->next;
        scanf("%d", &p->data);
    }
    p->next = NULL;
    return OK;
}

/***************************************************************
 *函数名称：   DestroyList
 *函数功能：如果线性表L存在，销毁线性表L，释放数据元素的空间，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status DestroyList(LinkList &L) {
    if (L == NULL)
        return INFEASIBLE;
    LinkList p, q;
    p = L->next;
    q = L;
    while (p) {
        free(q);
        q = p;
        p = p->next;
    }
    free(q);
    L = NULL;
    return OK;
}

/***************************************************************
 *函数名称：   ClearList
 *函数功能：如果线性表L存在，删除线性表L中的所有元素，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ClearList(LinkList &L) {
    if (L == NULL)
        return INFEASIBLE;
    LinkList p, q;
    p = L->next->next;
    q = L->next;
    while (p) {
        free(q);
        q = p;
        p = p->next;
    }
    free(q);
    L->next = NULL;
    return OK;
}

/***************************************************************
 *函数名称：ListEmpty
 *函数功能：如果线性表L存在，判断线性表L是否为空，空就返回TRUE，否则返回FALSE；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListEmpty(LinkList L) {

    if (L == NULL)
        return INFEASIBLE;
    if (L->next == NULL)
        return OK;
    else
        return FALSE;
}

/***************************************************************
 *函数名称：ListLength
 *函数功能：如果线性表L存在，返回线性表L的长度，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
int ListLength(LinkList L) {
    if (L == NULL)
        return INFEASIBLE;
    int len = 0;
    LinkList p;
    p = L->next;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

/***************************************************************
 *函数名称：GetElem
 *函数功能：如果线性表L存在，获取线性表L的第i个元素，保存在e中，返回OK；如果i不合法，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status GetElem(LinkList L, int i, ElemType &e) {

    if (L == NULL)
        return INFEASIBLE;
    LinkList p;
    p = L;
    if (i == 0)
        return ERROR;
    while (p && i) {
        i--;
        p = p->next;
    }
    if (p == NULL)
        return ERROR;
    else
        e = p->data;
    return OK;
}

/***************************************************************
 *函数名称：LocateElem
 *函数功能：如果线性表L存在，查找元素e在线性表L中的位置序号；如果e不存在，返回ERROR；当线性表L不存在时，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status LocateElem(LinkList L, ElemType e) {

    if (L == NULL)
        return INFEASIBLE;
    LinkList p;
    p = L->next;
    int i = 1;
    while (p) {
        if (e == p->data) {
            return i;
        }
        i++;
        p = p->next;
    }
    return ERROR;
}

/***************************************************************
 *函数名称：PriorElem
 *函数功能：如果线性表L存在，获取线性表L中元素e的前驱，保存在pre中，返回OK；如果没有前驱，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status PriorElem(LinkList L, ElemType e, ElemType &pre) {

    if (L == NULL)
        return INFEASIBLE;
    LinkList p, q;
    p = L->next;
    q = L;
    while (p) {
        if (e == p->data) {
            break;
        }
        q = p;
        p = p->next;
    }
    if (p == NULL || q == L)
        return ERROR;
    pre = q->data;
    return OK;
}

/***************************************************************
 *函数名称：NextElem
 *函数功能：如果线性表L存在，获取线性表L元素e的后继，保存在next中，返回OK；如果没有后继，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status NextElem(LinkList L, ElemType e, ElemType &next) {
    if (L == NULL)
        return INFEASIBLE;
    if (L->next == NULL)
        return ERROR;
    LinkList p = L->next;
    while (p->next) {
        if (p->data == e)
            break;
        p = p->next;
    }
    if (p->next == NULL || p == NULL)
        return ERROR;
    else
        next = p->next->data;
    return OK;
}

/***************************************************************
 *函数名称：ListInsert
 *函数功能：如果线性表L存在，将元素e插入到线性表L的第i个元素之前，返回OK；当插入位置不正确时，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListInsert(LinkList &L, int i, ElemType e) {
    if (L == NULL)
        return INFEASIBLE;
    if (i <= 0 || i > ListLength(L) + 1)
        return ERROR;
    LinkList p = L;
    for (i; i > 1; i--) {
        p = p->next;
    }
    LinkList np;
    np = (LinkList)malloc(sizeof(LNode));
    np->data = e;
    if (p->next == NULL) {
        np->next = NULL;
        p->next = np;
    } else {
        np->next = p->next;
        p->next = np;
    }
    return OK;
}

/***************************************************************
 *函数名称：ListDelete
 *函数功能：如果线性表L存在，删除线性表L的第i个元素，并保存在e中，返回OK；当删除位置不正确时，返回ERROR；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListDelete(LinkList &L, int i, ElemType &e) {
    if (L == NULL)
        return INFEASIBLE;
    if (i <= 0)
        return ERROR;
    LinkList p = L;
    while (p && i) {
        i--;
        p = p->next;
    }
    if (p == NULL)
        return ERROR;
    LinkList q = L;
    while (q->next != p) {
        q = q->next;
    }
    e = p->data;
    q->next = p->next;
    free(p);
    return OK;
}

/***************************************************************
 *函数名称：ListTraverse
 *函数功能：如果线性表L存在，依次显示线性表中的元素，每个元素间空一格，返回OK；如果线性表L不存在，返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status ListTraverse(LinkList L) {
    if (L == NULL)
        return INFEASIBLE;
    LinkList p = L->next;
    if (p == NULL)
        return OK;
    printf("%d", p->data);
    while (p->next) {
        p = p->next;
        printf(" %d", p->data);
    }
    printf("\n");
    return OK;
}

/***************************************************************
 *函数名称：SaveList
 *函数功能：如果线性表L存在，将线性表L的的元素写到FileName文件中，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status SaveList(LinkList L, char FileName[]) {
    if (L == NULL)
        return INFEASIBLE;
    FILE *fp;
    fp = fopen(FileName, "w");
    if (fp == NULL)
        return ERROR;
    LinkList p = L->next;
    while (p) {
        fprintf(fp, "%d ", p->data);
        p = p->next;
    }
    fclose(fp);
    return OK;
}

/***************************************************************
 *函数名称：LoadList
 *函数功能：如果线性表L不存在，将FileName文件中的数据读入到线性表L中，返回OK，否则返回INFEASIBLE。
 *返回值类型：status
 ****************************************************************/
status LoadList(LinkList &L, char FileName[]) {
    if (L != NULL) {
        DestroyList(L);
    }
    FILE *fp;
    fp = fopen(FileName, "r");
    if (fp == NULL)
        return ERROR;
    L = (LinkList)malloc(sizeof(LNode));
    LinkList p;
    p = (LinkList)malloc(sizeof(LNode));
    p = L;
    int tem;
    while (fscanf(fp, "%d", &tem) != EOF) {
        p->next = (LinkList)malloc(sizeof(LNode));
        p = p->next;
        p->data = tem;
    }
    p->next = NULL;
    fclose(fp);
    return OK;
}

/***************************************************************
 *函数名称：reverseList
 *函数功能：初始条件是线性表L已存在,否则返回INFEASIBLE；操作结果是将L翻转；
 *返回值类型：status
 ****************************************************************/
status reverseList(LinkList L) {
    if (L == NULL)
        return INFEASIBLE;
    LinkList p = L->next->next, q = L->next;
    while (p != NULL) {
        q->next = p->next;
        p->next = L->next;
        L->next = p;
        p = q->next;
    }
    return OK;
}

/***************************************************************
 *函数名称：RemoveNthFromEnd
 *函数功能：初始条件是线性表L已存在且非空，否则返回INFEASIBLE, 操作结果是删除该链表中倒数第n个节点；
 *返回值类型：status
 ****************************************************************/
status RemoveNthFromEnd(LinkList L, int n) {
    if (L == NULL)
        return INFEASIBLE;
    n = ListLength(L) - n;
    if (n <= 0 || n > ListLength(L))
        return ERROR;
    LinkList p = L->next, q = L;
    for (int i = 0; i < n && p; i++, q = q->next, p = p->next)
        ;
    q->next = p->next;
    free(p);
    return OK;
}

/***************************************************************
 *函数名称：sortList
 *函数功能：初始条件是线性表L已存在，否则返回INFEASIBLE；操作结果是将L由小到大排序；
 *返回值类型：status
 ****************************************************************/
status sortList(LinkList L) {

    if (L == NULL)
        return INFEASIBLE;
    LinkList p = L->next, q = L->next;
    for (p; p != NULL; p = p->next) {
        for (q = L->next; q != p; q = q->next) {
            if (q->data > p->data) {
                ElemType tem = p->data;
                p->data = q->data;
                q->data = tem;
            }
        }
    }
    return OK;
}